package com.example.hot100;

/**
 * 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
 *  现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。
 *  这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
 *  求所能获得硬币的最大数量。
 *  题解参考:https://leetcode-cn.com/problems/burst-balloons/solution/zhe-ge-cai-pu-zi-ji-zai-jia-ye-neng-zuo-guan-jian-/
 *
 * 示例 1：
 * 输入：nums = [3,1,5,8]
 * 输出：167
 * 解释：
 * nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
 * coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167
 *
 *  示例 2：
 * 输入：nums = [1,5]
 * 输出：10
 */
public class Leetcode312_MaxCoins {
    public static void main(String[] args) {
        int[] nums = {3, 1, 5, 8};
        System.out.println(new Solution().maxCoins(nums));
    }

    static class Solution {

        /**
         * 动态规划:
         * 先在原数组头尾各加上一个 1 得到vals数组(主要是为了好处理边界情况)
         * dp[i][j]表示戳破开区间(i, j)能获得的最多金币数
         * 假设 k 为整个区间k最后一个被戳爆的气球
         * 则：dp[i][j] = dp[i][k] + num(k) + dp[k][j]
         * 其中 num(k) = val[i] * val[k] * val[j]
         * @param nums
         * @return
         */
        public int maxCoins1(int[] nums) {
            int n = nums.length;
            int[] vals = new int[n + 2]; // 在原数组的首尾分别加上一个1，方便处理边界情况
            for (int i = 1; i < n + 1; i++) {
                vals[i] = nums[i - 1];
            }
            vals[0] = 1;
            vals[n + 1] = 1;
            int[][] dp = new int[n + 2][n + 2]; // dp[i][j]表示戳破开区间(i, j)能获得的最多金币数

            for(int len = 3; len <= n + 2; len++){// len表示开区间长度
                // i表示开区间左端点
                for(int i = 0; i <= n + 2 - len; i++){
                    int res = 0;
                    // k为开区间内的索引
                    for(int k = i + 1; k < i + len - 1; k++){
                        int left = dp[i][k];
                        int right = dp[k][i + len - 1];
                        res = Math.max(res, left + (vals[i] * vals[k] * vals[i + len - 1]) + right);
                    }

                    dp[i][i + len - 1] = res;
                }
            }

            return dp[0][n + 1];
        }

        public int maxCoins(int[] nums) {
            return maxCoins1(nums);
        }
    }
}
